package com.algorithm.kmp;

import java.util.Arrays;

public class Kmp {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ADBCDABCDABDE";
        String str2 = "ABCDABD";

        int[] next = getKmpNext(str2);
        int index = KMPSearch(str1, str2, next);
        System.out.println(index);
    }

    /**
     * 暴力匹配算法:匹配成功后返回对应的下标，否则返回-1
     */
    public static int ViolenceMath(String str1,String str2){
        char s1[]  = str1.toCharArray();
        char s2[] = str2.toCharArray();
        int s1Len = s1.length;
        int s2Len = s2.length;
        //索引
        int i = 0;
        int j = 0;
        while(i<s1Len && j<s2Len){
            if(s1[i] == s2[j]){
                i++;
                j++;
            }else {
                i = i - j + 1;
                j = 0;
            }
        }
        //判断是否匹配成功，如果成功则此时j的长度为s2的长度
        if( j == s2Len){
            return i - j;
        }
        return  -1;
    }

    /**
     * KMP算法，返回第一个匹配的位置，匹配失败返回-1
     */
    public static int KMPSearch(String str1,String str2,int[] next){
        // i为str1的索引，j为str2的索引
        for(int i = 0,j = 0;i<str1.length();i++){
            while(j > 0 && str1.charAt(i) != str2.charAt(j)){
                // i= i -j +( j - next[j-1]);
                // j = 0;
                j = next[j-1];
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if(j == str2.length()){
                return i - j + 1;
            }
        }
        return  -1;
    }
    /**
     * 获取子串的部分匹配表
     */
    public static int[] getKmpNext(String dest){
        int[] next = new int[dest.length()];
        //字符串长度为1时，部分匹配值即为0
        next[0] = 0;
        for(int i = 1,j = 0;i<dest.length();i++){
            while(j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}
